package code.oldCode.feishuSpecializedTraining.greedy;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 26029
 * @date 2025/3/19
 * @description
 */
public class MyGreedy3 {
    // 1005. K 次取反后最大化的数组和
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 模拟：常规解法，复杂度O(len * k)，每次找最小值
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        for (int i = 0; i < k; i++) {
            int min = nums[0];
            int minPos = 0;
            for (int j = 1; j < len; j++) {
                if (nums[j] < min) {
                    minPos = j;
                    min = nums[j];
                }
            }
            nums[minPos] = -nums[minPos];
        }
        return Arrays.stream(nums).sum();
    }

    public int largestSumAfterKNegations_heap(int[] nums, int k) {
        // 使用堆排序-优先队列的做法 O(nlog2n)
        if (nums == null || nums.length == 0)
            return 0;
        int sum = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.offer(num);
            sum += num;
        }
        for (int i = 0; i < k; i++) {
            int poll = queue.poll();
            sum = sum - 2 * poll;
            queue.offer(-poll);
        }
        return sum;
    }

    public int largestSumAfterKNegations_sort(int[] nums, int k) {
        // 使用sort先排序，然后找负的 [3,-1,0,2]，复杂度也是O(nlog2n)
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        for (int i = 0; i < len; i++) {
            if (nums[i] >= 0)
                break;
            // num < 0 的情况，消耗一个k把他变正，如果k用完了，直接返回结果即可
            if (k == 0)
                return sum;
            sum -= 2 * nums[i];
            nums[i] = -nums[i];
            k--;
        }
        // 如果k还剩偶数个，直接返回结果
        if (k % 2 == 0)
            return sum;
        // 如果k剩奇数个，把最小的那个非负数换为负数
        Arrays.sort(nums);
        return sum - 2 * nums[0];
    }

    // 134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 解是唯一的
        int len = gas.length;
        // 遍历起始位置
        // gas  [1,2,3,4,5]
        // cost [3,4,5,1,2]
        for (int i = 0; i < len; i++) {
            int pos = i, end = i + len - 1;
            int nowGas = 0;
            int count = 0;
            while (pos <= end) {
                nowGas += gas[pos % len];
                if (nowGas >= cost[pos % len]) {
                    nowGas -= cost[pos % len];
                    pos++;
                    count++;
                } else {
                    break;
                }
            }
            if (count == len)
                return i;
            // 这一步是因为，如果到了这一步说明这个i不成立，不必到i+1
            // 到pos即可，因为是在pos位置不成立的，说明i~pos都不成立，下一步直接从pos+1开始
            i = pos;
        }
        return -1;
    }

    // 135. 分发糖果
    public int candy(int[] ratings) {
        // 两次遍历
        int len = ratings.length;
        if (len <= 1)
            return len;
        int[] candies = new int[len];
        Arrays.fill(candies, 1);
        // 第一次遍历，符合他比左面大的时候的规则
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        // 第二次遍历，符合他比右面大的时候的规则，同时注意，可能已经符合规则了就不要改了
        int ans = candies[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])
                candies[i] = candies[i + 1] + 1;
            ans += candies[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        MyGreedy3 m = new MyGreedy3();
        System.out.println(m.canCompleteCircuit(new int[]{1,2,3,4,5}, new int[]{3,4,5,1,2}));
    }
}
